This invention is relates to cryptosystems and, more particularly, to "public-key" cryptosystems. Cryptosystems in which messages are encrypted by the sender and decrypted, or deciphered, by the receiver have been well known for some time. In conventional cryptosystems, when a network user has desired to transmit a message to a particular destination, the receiver must first inform the sender of the receiver's cryptograhpic key. The encryption and decryption keys were identical and, therefore, both must be kept secret from the public, as it would otherwise be possible for the message to be intercepted and easily deciphered.
An improvement on the conventional cryptosystem was the public-key cryptosystem first introduced by W. Diffie and M. Hellman, "New Directions in Cryptography," IEEE Transactions on Information Theory, November 1976, pp. 644-654. In contrast to conventional cryptosystems in which encryption and decryption keys were identical, the public-key cryptosystem utilizes encryption and decryption keys which are quite distinct. The encryption keys may be available to the public so that any sender may encode and transmit his message, but only the receiver can decipher the message since he is the only person having access to the secret decryption key. In order for such a system to work, it is obviously necessary that the encryption and decryption keys be so designed that it is computationallyunfeasible to obtain the decryption key from the encryption key. This has presented considerable problems. The security of the decryption key may be assured by utilizing very complicated encryption and decryption algorithms, but this will result in a consequent decrease in both signal processing speed and transmission capacity. On the other hand, simplifying the algorithms might expose the decryption key to attack by highly sophisticated computerized cryptanalysis techniques.
Several public-key cryptosystems have been proposed. A first public-key cryptosystem is disclosed by R. Rivest, A. Shamir and L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," Communications of the ACM, Vol. 21, No. 2, February 1978, pp. 120-126. This first system makes use of the fact that there is no kown efficient algorithm for factoring a composite number into prime factors. Both encryption and decryption algorithms use exponentiation modulo (a large composite number) and the task of cryptanalysis appears to be equivalent to factoring the large composite number. Although this first system appears elegant, its encryption and decryption operations, namely, exponentiation modulo (a large composite number), are relatively complex. Its computing time is approximately T(r) log.sub.2 r, where r is the composite number used in the system and T(r) is the time required to multiply two numbers modulo r. Due to the complexity of the system and long computing-time requirements, this system is somewhat limited to low speed data rate communication systems.
A second system is disclosed by R. Merkle and M. Hellman, "Hiding Information and Receipts in Trap Door Knapsacks," paper presented at the 1977 IEEE International Symposium on Information Theory, Oct. 10-14, 1977, Cornell Universty, Ithaca, N.Y. This second system makes use of the fact that knapsacks problems are generally difficult to solve. (In this system there are two known sets of integers, but the transformation factor for converting the first set to the second set is unknown. The "knapsack" problem is to find the proper mapping between the two sets of integers by finding a subset of numbers, if there is such a subset, that adds up to a given number.) The encryption operation consists only of additions and the decryption operation consists of (multiplication of two numbers modulo (a number), comparisons and substractions. The task of cryptanalysis appears to be difficult because the knapsack problem belongs to the class of NP-complete problems, "NP-complete" being a term of art which refers to a problem the solution to which will also be the solution to all others within the same class of problems. Although both encryption and decryption operatons in this system are relatively simple, it is characterized by a message (or bandwidth) expansion factor of at least two.
A third proposed cryptosystem is disclosed by R. McEliece, "A Public-Key Cryptosystem Based on Algebraic Coding Theory," JPL Deep Space Network Progress Report 1978. This system makes use of the fact that an efficient decoding algorithm does exist for a general Goppa code, but no such algorithm is known for a general linear code. The encryption process consists of encoding with a linear code and then interfering the code word with a controlled noise generator. The decryption process is more complicated, essentially consisting of a decoding process for Goppa codes. The task of cryptanalysis appears to be difficult for this system, since the general problem of decoding a linear code is also an NP-complete problem. The disadvantage of this third system is that the implementation complexities of both the encryption process and the decryption process are very high, even with today's technology. Thus, its application is somewhat limited.